/*
题目: 统计定界子数组的数目
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。

nums 的定界子数组是满足下述条件的一个子数组：

    子数组中的 最小值 等于 minK 。
    子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。

https://leetcode.cn/problems/count-subarrays-with-fixed-bounds
 */
public class CountSubarrays {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long src = 0;
        int n = nums.length;
        // 分别表示 maxK 和 minK 的下标, 和最近一次不满足区间的下标
        int maxIdx = -1, minIdx = -1, idx0 = -1;

        // 每次对满足题意区间的最后一个元素做结算
        // 因为子数组的长度至少为 [Math.min(maxIdx, minIdx), i] 的区间, 所以以最后一个元素
        // 作为结算的子数组个数就为 Math.min(maxIdx, minIdx) - idx0
        for (int i = 0; i < n; i ++) {
            if (nums[i] == maxK) maxIdx = i;
            if (nums[i] == minK) minIdx = i;
            // 区间作废
            if (nums[i] < minK || nums[i] > maxK) idx0 = i;

            // 如果这个区间有效, 长度至少为正
            // 如果数组一直都符合这个区间, idx0 初始化为 0 比较方便
            src += Math.max(Math.min(maxIdx, minIdx) - idx0, 0);
        }

        return src;
    }
}
